/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        if (head == nullptr) {
            cout << "NULL\n";
            return nullptr;
        }
        if (head->next == nullptr) return head;
        ListNode *rev_head = reverseList(head->next);
        ListNode *rev_tail = rev_head;
        while (rev_tail && rev_tail->next != nullptr)
            rev_tail = rev_tail->next;
        rev_tail->next = head;
        head->next = nullptr;
        return rev_head;
    }
};

void printlist(ListNode *head) {
    while (head) {
        cout << head->val << "->";
        head = head->next;
    }
    cout << "NULL\n";
}

int main() {
    ListNode *p1 = new ListNode;
    ListNode *p2 = new ListNode;
    ListNode *p3 = new ListNode;
    ListNode *p4 = new ListNode;
    ListNode *p5 = new ListNode;
    p1->val = 1;
    p2->val = 2;
    p3->val = 3;
    p4->val = 4;
    p5->val = 5;
    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = p5;
    p5->next = nullptr;
    Solution s;
    printlist(s.reverseList(p1));
}